The Twofish Encryption Algorithm: A 128-Bit Block Cipher The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson
Wiley Computer Publishing, John Wiley & Sons, Inc.
ISBN: 0471353817   Pub Date: 03/01/99
  

Previous Table of Contents Next


Chapter 8
Design of the Twofish Key Schedule

The key schedule for Twofish is a really a huge piece by itself. While it reuses many of the components of the cipher, it also required a significant amount of independent engineering. This chapter addresses the issues we came across in designing the key schedule.

To understand the design of the key schedule, it is necessary to consider how key material is used in Twofish:

The Whitening Subkeys. A whitening subkey of 128 bits is XORed into the plaintext block before encryption, and another 128 bits subkey after encryption. Since the rest of the encryption is a permutation, this can be seen as selecting among as many as 2256 different (but closely related) 128-bit to 128-bit permutations for the whole cipher. This key material has the effect of making many cryptanalytic attacks a little more difficult at a very low cost. Note that nearly all the added strength against cryptanalytic attack is added by the XOR of subkeys into the input to the first and last rounds’ F functions.
The Round Subkeys. Each round, 64 bits of key material are combined into the output of the F function using addition modulo 232. The F function without the round subkey addition is a permutation on 64-bit values; the round subkey selects among one of 264 closely related permutations in each round. These subkeys must be slightly different per round to prevent a slide attack, as will be discussed below.
The Key-dependent S-boxes. To create the S-boxes, the key is mapped down to a block of data half its size, S, and that block of data is used to specify the S-boxes for the whole cipher. As discussed earlier, the key-dependent S-boxes are derived by alternating fixed S-box lookups with XORs of key material. The key-dependent S-boxes define one of 2L/2 possible permutations for the g function, where L is the number of bits in the cipher key. Unlike the other keys used, different S values typically lead to radically different g functions.

8.1 Round Subkeys

8.1.1 Equivalence of Round Subkeys

In this section, we discuss whether different sequences of subkeys can give equivalent encryption functions. Recall that F´ is the F function without the addition of the round subkeys, which takes two 32-bit words as input and produces two 32-bit words as output. For this analysis we keep the function F´ constant. That is, we only vary the subkeys Ki and not S.

The properties of a Feistel cipher ensure that no pair of 2-round subkey sequences can be equivalent for all inputs. It is natural to ask next whether any pairs of three sequential rounds’ subkeys can exist that cause exactly the same encryption.

For a pair of subkey sequences, (k0, k1, k2) and (k*0, k*1, k*2), to be equivalent in their effects, every input block (L0, R0) must encrypt to the same output block (L1, R2) for both sequences of subkeys. Note that k0k*0 and k2k*2, as we would otherwise have two sequences of 2-round keys that would define the same 2-round encryption function. We have the following equalities:

R1 = R0 ⊕ (k0 + F´(L0))

R*1 = R0 ⊕ (k*0 + F´(L0))

L1 = L0 ⊕ (k1 + F´(R1))

L1 = L0 ⊕ (k*1 + F´(R*1))

R2 = R1 ⊕ (k2 + F´(L1))

R2 = R*1 ⊕ (k*2 + F´(L1))

where ⊕ represents bitwise XORing, and + represents 32-bit componentwise addition. Using the two equations for L1 we get

k1 + F´(R1) = k*1 + F´(R*1)

δ1 = F´(R1) - F´(R*1)

where δ1 = k*1 - k1 is fixed. Let T = F´ (L0) + k0 and observe that when L0 goes over all possible values, so does T. We get

δ1 = F´(R0T) - F´(R0 ⊕ (T + δ0)) (8.1)

where δ0 = k*0 - k0. Note that δ1 and δ0 depend only on the round keys, and that the equation must hold for all values of R0 and T. Set T = 0 and look at the cases R0 = 0 and R0 = δ0. We get

F´(0) - F´(δ0) = δ1 = F´(δ0) - F´(0) = - δ1

The subtraction here is modulo 232 for each of the two 32-bit words. That leaves us with the following possible values for δ1:

δ1 ∈ {(0,0), (0,231), (231,0), (231,231)}

These are the possible difference values at the output of F´ in equation 8.1. We can easily convert them to difference values at the input of the PHT of F´. Each of the possible values for δ1 corresponds to exactly one possible value for (δT0, δT1):

(δT0, δT1) ∈ {(0,0), (0,231), (231,0), (231,231)}

We can write down the analogue to equation 8.1 for g:

δT0 = g(R´T´) - g(R´ ⊕ (T´ + δ´0))

for all and and where δ´0 is the appropriate half of δ0. Observe that for the specific values of δT0 that are possible, subtraction and XOR are the same. For = 0 this translates in a simple differential equation

δT0 = g(R´) ⊕ g(R´δ´0)

for all . We know that g has only one perfect differential: 0 → 0, so we conclude that δ´0 = 0. Similarly, we can conclude that the other half of δ0 must also be zero, and thus δ0 = 0. This is a contradiction, as k0k*0.

We conclude that there are no two sets of 3-round subkey sequences that result in the same encryption function.

A Conjecture about Equivalent Subkeys in Twofish. We believe that, for up to 16 rounds of Twofish, there are no pairs of round subkeys that (with the same function) result in the same encryption function. There simply do not appear to be enough degrees of freedom in choosing the different subkeys to make pairs of equivalent subkey sequences in as few as 16 rounds. However, we have been unable to prove this.

Note that this conjecture does not hold for an arbitrary number of rounds. Any fixed round function is an element of the permutation group on 128-bit values S2128. The order of this group is (2128)! ≈ 22134, and the order of any group element must be a divisor of the order of the group. Thus, any round function when iterated (2128)! times, results in the identity mapping.1 For this number of rounds there are thus many equivalent round subkeys.


1In fact, this property holds for any bijective function, including the complete Twofish encryption and the AES block cipher (irrespective of which candidate is chosen).

8.1.2 Equivalent keys

Can two keys generate the same sequence of round subkeys? We have performed exhaustive tests to show this is not the case. To generate the same round subkeys, the two keys will have to generate the same set of Ai and Bi.

We observe that Ai = h(2ρi, Me), where the h function consists of applying the MDS matrix multiplication to the four values (y0, y1, y2, y3) obtained by running the value 2i through 1 + N/64 levels of q0 and q0, XORing with bytes from Me. Since the MDS matrix is non-singular, it is easily seen that to generate the same sequence of Ai values, the keys must generate the same sequence of values for y0, y1, y2 and y3.


Previous Table of Contents Next